/**
 * 新增节点 (题目前提：val 一定与树中节点不同)
 * @author liuzhaoqiang
 */
public class E02Leetcode701 {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /*
            val=1

            5
           / \
          2   6
           \
            3
     */
    public TreeNode insertIntoBST(TreeNode node, int val) {
        if(node==null){
            return new TreeNode(val);
        }
        if(node.val>val){
            node.left = insertIntoBST(node.left,val);
        }else{
            node.right = insertIntoBST(node.right,val);
        }
        return node;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5, new TreeNode(2, null, new TreeNode(3)), new TreeNode(6));
        new E02Leetcode701().insertIntoBST(root, 1);
    }
}
